package com.tgy.algorithm.base;

import java.time.Period;

class PreTreeNode {
    int pass;
    int end;
    // 只插入 a-z的26个小写字母
    PreTreeNode[] nexts = new PreTreeNode[26];
}

// 前缀树
class PreTree {
    PreTreeNode root;

    public PreTree() {
        root = new PreTreeNode();
    }

    public void add(String str) {
        if (str == null || str.length() == 0) {
            return;
        }

        char[] charArray = str.toCharArray();
        root.pass++;
        PreTreeNode node = root;
        for(char aChar : charArray) {
            int index = aChar - 'a';
            PreTreeNode next = node.nexts[index];
            if (next == null) {
                next = new PreTreeNode();
                node.nexts[index] = next;
            }
            next.pass++;
            node = next;
        }
        node.end++;
    }

    public int search(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }

        char[] charArray = str.toCharArray();
        PreTreeNode node = root;
        PreTreeNode next = null;
        for (char aChar : charArray) {
            int index = aChar - 'a';
            next = node.nexts[index];
            if (next == null) {
                return 0;
            }
            node = next;
        }

        if (node.end >0) {
            return node.end;
        }

        return 0;
    }

    public int preNumber(String str) {
        if (str == null || str.isEmpty()) {
            return 0;
        }

        char[] charArray = str.toCharArray();
        PreTreeNode node = root;
        PreTreeNode next = null;
        for (char aChar : charArray) {
           int inex = aChar - 'a';
           next = node.nexts[inex];
           if (next == null) {
               return 0;
           }
           node = next;
        }

        return node.pass;
    }

    public void delete(String str) {
        if (str == null || str.length() == 0) {
            return;
        }

        // 如果树里面没有加这个字符串，则直接返回
        if(this.search(str) == 0) {
            return;
        }

        char[] charArray = str.toCharArray();
        PreTreeNode node = root;
        node.pass--;
        PreTreeNode next = null;
        for (char aChar : charArray) {
            int index = aChar - 'a';
            next = node.nexts[index];
            next.pass--;
            // 如果检查到这条路上pass减之后为0，则表示这条路上只有这一个字符串，则没有必要往下走
            if(next.pass == 0) {
                node.nexts[index] = null;
                return;
            }
            node = next;
        }

        /**
         *           ()
         *          a
         *          ()
         *
         *
         */
        node.end--;
    }
}

public class _前缀数01 {
    public static void main(String[] args) {
        PreTree tree = new PreTree();
        tree.add("ab");
        tree.add("abc");
        tree.add("abcde");
//        int abc = tree.search("abc");
//        System.out.println(abc);
//        int search = tree.search("ab");
//        System.out.println(search);
//
//        int preNum = tree.preNumber("ab");
//        System.out.println(preNum);

        tree.delete("abcde");
        int res = tree.search("abc");
        System.out.println(res);
    }
}
